#include<iostream>
#include<string>
#include<sstream>
#include<stdio.h>

using namespace std;

	bool primes[1000000];
	int digitPrimes[1000000];


	bool isDigitPrime(int i) {
		string integer;
		stringstream s;
		s << i;
		s >> integer;

		int number = 0;
		int length = integer.length();
		for (int k = 0; k < length; k++) {
			number += (int)(integer[k] - '0');
		}
//		System.out.println(i + " " + number + " " + primes[number]);
		return primes[number];
	}


 void createPrimes() {
         int i, j;

         for(i = 0; i < 1000000; i++) {
            primes [i] = false;
         }

         primes[2] = true;
         digitPrimes[2] = 1;
         primes[3] = true;
         digitPrimes[3] = 2;
         digitPrimes[4] = 2;
	 primes[5] = true;
         digitPrimes[5] = 3;
	 digitPrimes[6] = 3;
	 primes[7] = true;
	 digitPrimes[7] = 4;
         digitPrimes[8] = 4;

         for(i = 9; i < 1000000; i+=2) {
//        	 System.out.println("I: " + i);
             digitPrimes[i-1] = digitPrimes[i-2];
             digitPrimes[i] = digitPrimes[i-1];
//             System.out.println(">> " + digitPrimes[i-1]);
        	 for(j = 3; j*j <=i ; j+=2)
                 if(i % j == 0) break;
             if(i % j != 0 ) { 
            	 primes[i] = true;
             }
             if (primes[i] && isDigitPrime(i)) {
            	 digitPrimes[i]++;
             }
//             System.out.println(digitPrimes[i]);
         }
      }
	
	



	int main() {
		createPrimes();
		int aux;
		int cases;
		scanf("%d", &cases);
		for (int k = 0; k < cases; k++) {
			
			int x;
			int y;
			
			scanf("%d %d", &x, &y);
			
			if (x > y) {
				aux = x;
				x = y;
				y = aux;
			}

//			if ( x == y) {
//				cout << digitPrimes[x] << endl;
//			} else {
				printf("%d\n", (digitPrimes[y] - digitPrimes[x-1]));
//			}
		}
	}


